package algorithm_demo.leetcode;

/**
 * 3. 无重复字符的最长子串
 * <a href="https://leetcode.cn/problems/longest-substring-without-repeating-characters/">https://leetcode.cn/problems/longest-substring-without-repeating-characters/</a>
 * @author Api
 * @date 2023/4/6 1:03
 */
public class Problem_0003_LongestSubstringWithoutRepeatingCharacters {
    /*
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
     * 示例1:
     * 输入: s = "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * 示例 2:
     * 输入: s = "bbbbb"
     * 输出: 1
     * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
     * 示例 3:
     * 输入: s = "pwwkew"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
     * 请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
     * */


    public static int lengthOfLongestSubstring(String s) {
        if (s == null || "".equals(s)) {
            return 0;
        }
        char[] str = s.toCharArray();
        int[] dp = new int[256];
        //字符总共256个，主要是数组效率更高，相对于Map来说
        for (int i = 0; i < 256; i++) {  // 利用ascii码
            dp[i] = -1;
        }
        //收集答案
        int len = 0;
        int pre = -1;//i-1位置结尾的情况下，往左推，推不动的位置是谁
        int cur = 0;
        for (int i = 0; i != str.length; i++) {
            //i位置结尾的情况下，往左推，推不动的位置是谁
            //pre(i-1信息)  -> pre(i 结尾信息)
            pre = Math.max(pre, dp[str[i]]);
            //其实就是i减去离的最近的下标值
            cur = i - pre;
            len = Math.max(len, cur);
            dp[str[i]] = i;
        }
        return len;
    }
}
